package leetcode; /**
 * description:
 * author:zt
 * date:2021-07-30
 */

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
 *
 * 每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
 */
public class leetcode662 {
    int ans;
    Map<Integer,Integer> left;
    public int widthOfBinaryTree(TreeNode root) {
        ans = 0;//4.初始化该全局变量
        left = new HashMap();//2.初始化该全局变量。
        //根节点为第一层
        dfs(root, 1, 1);
        return ans;//5.返回结果
    }

    public void dfs(TreeNode root, int depth, int pos) {
        if (root == null) return;//6.递归终止条件。
        left.computeIfAbsent(depth, x -> pos);//9.添加最左侧的元素，当第一次走到某一层的时候，此时map里面是空，更新一次位置信息。
        ans = Math.max(ans, pos - left.get(depth) + 1);//10.计算当前结点跟最左侧结点位置的距离，并更新最大值。
        dfs(root.left, depth + 1, 2 * pos);//7.计算左孩子的位置并记录所在层级，在遇到同层级的最左侧元素就可以参与运算得出距离。
        dfs(root.right, depth + 1, 2 * pos + 1);//8.计算左孩子的位置并记录所在层级
    }
}
